#include <cstdio>
#include <iostream>
#include <type_traits>
#include <vector>
using namespace std;

using cvec = const vector<int>;
using vec = vector<int>;

int max_cost(cvec &W, cvec &C, vec &P, int w, int n)
{
	if (w == 0 || n == 0) {
		return 0;
	}

	int maxc = 0;
	if (P[n] == 0) {
		maxc = max_cost(W, C, P, w, n - 1);
		if (W[n] <= w) {
			maxc = max(maxc, max_cost(W, C, P, w - W[n], n) + C[n]);
		}
	} else {
		maxc = max_cost(W, C, P, w, n - 1);
		for (int i = 1; i <= P[i]; i++) {
			if (W[n] * i <= w) {
				maxc = max(maxc, max_cost(W, C, P, w - W[n] * i, n - 1) + C[n] * i);
			}
		}
	}
	return maxc;
}
int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);

	int W, N;
	cin >> W >> N;

	vector<int> w(N + 1, 0);
	vector<int> c(N + 1, 0);
	vector<int> p(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		cin >> w[i] >> c[i] >> p[i];
	}
	cout << max_cost(w, c, p, W, N) << endl;
	return 0;
}